
let KMP = {
    normalSearch: function (ori, str) { 
        let oLen = ori.length;
        let mLen = str.length;
        let i = 0, j = 0;
        while (i < oLen && j < mLen) {
            if (ori[i] == str[j]) {
                i++;
                j++
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j == mLen) {
            return i - j;
        } else {
            return -1;
        }
    },

    getKmpNextArr: function (ori) { 
        let oLen = ori.length;
        let next = [];
        next[0] = -1;
        let k = -1, j = 0;
        while (j < oLen - 1) {
            // ori[k]表示前缀，ori[j]表示后缀
            if (k == -1 || ori[j] == ori[k]) {
                ++j;
                ++k;            
                if (ori[j] != ori[k]) {
                    next[j] = k;
                }
                else {
                    next[j] = next[k];
                }
            }
            else {
                k = next[k];
            }
        }
        return next;
    },

    KmpSearch: function (ori, str) { 
        let oLen = ori.length;
        let mLen = str.length;
        let i = 0, j = 0;
        let next = this.getKmpNextArr(ori);
        while (i < oLen && j < mLen) {
            if (j == -1 || ori[i] == str[j]) {
                i++;
                j++
            } else {
                j = next[j];
            }
        }
        if (j == mLen) {
            return i - j;
        } else {
            return -1;
        }
    },
};

let str1 = "abc abce abcdef";
let str2 = "abcd";
let idx = -1;

console.log("normal:")
idx = KMP.normalSearch(str1, str2);
if (idx >= 0) {
    console.log(idx, str1.substring(idx, idx + str2.length))
} else {
    console.log("none");
}

console.log("kmp:")
idx = KMP.KmpSearch(str1, str2);
if (idx >= 0) {
    console.log(idx, str1.substring(idx, idx + str2.length))
} else {
    console.log("none");
}